package leetcode3;

import java.util.*;

public class test8 {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();

        List<Integer> res = new ArrayList<>();
        for(char c:p.toCharArray()){
            need.put(c, need.getOrDefault(c,0)  + 1);
        }
        int l = 0,r = 0;
        int valid = 0;
        if(s.length() < p.length())return new ArrayList<>();
        while (r < s.length()){
            char c = s.charAt(r);
            r++;
            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c,0) + 1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            while (r - l >= p.length()){
                if(valid == need.size()){
                    res.add(l);
                }
                char d = s.charAt(l);
                l++;
                if(need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return res;
    }
    public String minWindow(String s, String t) {
         Map<Character,Integer> need = new HashMap<>();
         Map<Character,Integer> window = new HashMap<>();


         for(char c:t.toCharArray()){
             need.put(c,need.getOrDefault(c,0) + 1);
         }
         int l = 0,r = 0;
         int valid = 0;

         int len = Integer.MAX_VALUE,start = 0;
         while (r  < s.length()){
             char c = s.charAt(r);
             r++;
             if(need.containsKey(c)){
                 window.put(c,window.getOrDefault(c,0) + 1);
                 if(window.get(c).equals(need.get(c))){
                     valid++;
                 }
             }
             while (valid == need.size()){
                 if(r - l < len){
                     start = l;
                     len = r - l;
                 }
                 char d = s.charAt(l);
                 l++;
                 if(need.containsKey(d)){
                     if(window.get(d).equals(need.get(d))){
                         valid--;
                     }
                     window.put(d,window.get(d) - 1);
                 }
             }
         }

         return len == Integer.MAX_VALUE?"":s.substring(start,start + len);
    }
}
